/*
day125
2019.12.31
*/
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
	bool isExit(vector<int>& nums,int target,int l,int r)
	{
		while(l<=r)
		{
			int mid=l+(r-l)/2;
			
			if(nums[mid]==target) return true;
			
			if(nums[mid]<target) l=mid+1;
			
			else 
			{
				r=mid-1;
			}
		}
		
		return false;
	}
	
	
    bool search(vector<int>& nums, int target) 
	{
        int l=0,r=nums.size()-1;
        int mid;
        while(l<=r)
        {
			mid=l+(r-l)/2;
//			cout<<mid<<endl;
			if(nums[mid]==target) return true;
			 
			 
			if(nums[l] ==nums[mid])
			{
				if(nums[l] == target) return true;
				int tem=nums[l];
				while(l<=r && nums[l] == tem) l++;
				continue;
			}
			
			else if(nums[l] < nums[mid])
			{
				if( target<=nums[mid] && target>=nums[l])
				{
					return this->isExit(nums,target,l,mid);
				}
				else
				{
					l=mid+1;
					continue;
				}
			}
			
			else //nums[l] > nums[mid]
			{
				if(target<=nums[r] && target>=nums[mid])
				{
					return this->isExit(nums,target,mid,r);
				}
				else
				{
					r=mid-1;
					continue;
				}
			}
		}
		
		return false;
    }
};



class Solution2 {
public:
    bool search(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++)
        {
        	if(nums[i]==target)
        	{
        		return true;
			}
		}
		return false;
    }
};


int main()
{
	vector<int> nums={1};
	int target=0;
	Solution s;
	cout<<s.search(nums,target)<<endl; 
	return 0;
}
